'''
https://leetcode.cn/problems/find-all-people-with-secret/description/
'''
from typing import List


class UnionFindSet:
    def __init__(self, n):
        self.father = [i for i in range(n)]

    def find(self, i):
        if self.father[i] != i:
            self.father[i] = self.find(self.father[i])
        return self.father[i]

    def is_same_set(self, i, j):
        return self.find(i) == self.find(j)

    def union(self, i, j):
        self.father[self.find(i)] = self.find(j)

    def detach(self, i):
        self.father[i] = i


class Solution:
    def findAllPeople(self, n: int, meetings: List[List[int]], firstPerson: int) -> List[int]:
        ufs = UnionFindSet(n)
        ufs.union(0, firstPerson)
        meetings.sort(key=lambda x: x[2])
        l = r = 0
        while r < len(meetings):
            while r < len(meetings) and meetings[r][2] == meetings[l][2]:
                r += 1
            # [l~r) 时刻这些人开会
            for i in range(l, r):
                ufs.union(meetings[i][0], meetings[i][1])
            # 不知道秘密的人，把他们从所在的集合拆掉
            for i in range(l, r):
                if not ufs.is_same_set(0, meetings[i][0]):
                    ufs.detach(meetings[i][0])
                if not ufs.is_same_set(0, meetings[i][1]):
                    ufs.detach(meetings[i][1])
            l = r = r
        res = []
        for i in range(n):
            if ufs.is_same_set(0, i):
                res.append(i)
        return res

n = 6
meetings = [[1,2,5],[2,3,8],[1,5,10]]
firstPerson = 1
print(Solution().findAllPeople(n, meetings, firstPerson))
